/*
有2^k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：
1、每个选手必须与其他n-1个选手各赛一次
2、每个选手一天只能赛一次
3、循环赛在n-1天内结束
*/
#include<iostream>
using namespace std;
#define MAX 101

int k;

// 存放比赛日程表（行列下标为0的元素不用）
int a[MAX][MAX];	 // 第i个选手在第j天与a[i][j]比赛

void Plan11(int k)
{
	// 求解2个选手比赛日程
	if(k==1)
	{	a[1][1]=1; a[1][2]=2;
		a[2][1]=2; a[2][2]=1;
	}
	else
	{
		Plan11(k-1);
		int n = 1<<(k-1);
		
		// 填左下角元素
		for (int i=n+1; i<=2*n; i++ )
			for (int j=1; j<=n; j++)
				a[i][j] = a[i-n][j]+n; 		//左下角元素和左上角元素的对应关系
			
		// 填右上角元素
		for (int i=1; i<=n; i++)
			for (int j=n+1; j<=2*n; j++)
				a[i][j] = a[i+n][(j+n)%(2*n)];
			
		// 填右下角元素
		for (int i=n+1; i<=2*n; i++)
			for (int j=n+1; j<=2*n; j++)
				a[i][j] = a[i-n][j-n];
	}
}

// 递归算法：求解循环日程安排问题
void Plan1(int k)
{
	Plan11(k);
}

// 迭代算法：求解循环日程安排问题
void Plan2(int k)
{
	// n从2^1=2开始
	int n = 2;
	
	// 求解2个选手比赛日程,得到左上角元素
	a[1][1]=1; a[1][2]=2;
	a[2][1]=2; a[2][2]=1;
	
	// 迭代处理,依次求2^2，…,2^k个选手的安排 
	for (int t=1; t<k; t++)
	{
		// tmp=2^t
		int tmp = n;
		
		// n=2^(t+1)
		n=n*2;
		
		// 填左下角元素
		for (int i=tmp+1; i<=n; i++ )
			for (int j=1; j<=tmp; j++)
				a[i][j] = a[i-tmp][j]+tmp; 	// 左下角元素和左上角元素的对应关系
			
		// 填右上角元素
		for (int i=1; i<=tmp; i++)
			for (int j=tmp+1;j<=n; j++)
				a[i][j] = a[i+tmp][(j+tmp) % n];
			
		// 填右下角元素
		for (int i=tmp+1; i<=n; i++)	
			for (int j=tmp+1; j<=n; j++)
				a[i][j] = a[i-tmp][j-tmp];
	}
}

int main()
{
	k = 3;
	int n=1<<k; // n等于2的k次方即n=2^k
	
	// 打印
	printf("n=%d\n",n);
	printf("递归算法:\n");
	
	// 产生n个选手的比赛日程表
	Plan1(k);
	
	// 输出比赛日程表
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
			printf("%4d", a[i][j]);
		printf("\n");
	}
	
	// 产生n个选手的比赛日程表
	printf("迭代算法:\n");
	Plan2(k);
	
	// 输出比赛日程表
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
			printf("%4d", a[i][j]);
		printf("\n");
	}
	
	return 0;
}
